/**
 * 如果x是回文数且能被k整除，称之为k回文数。
 * 如果x通过重新排列数位能够变成k回文数，称为好的
 * 问N个数位的整数中有多少个好的整数
 * 
 * 赛时用数位DP做，但是错的。因为数位DP统计的是自身是k的倍数的数，而不是调整以后是k的倍数的数
 * 考虑到N最大到10，可以直接统计。
 * 
 * 例如假设N是8，则
 * for i in range(1000, 9999):
 *     对每一个i，将其转置接起来，于是得到一个回文数，记作h
 *     if 0 == h % K:
 *         将其按数位排序记作key
 *         如果key已经处理过: continue
 *         计算能够调整为h的数，用排列乘除即可
 */
class Solution {

using llt = long long;
using vi = vector<int>;
vi Candi;
llt Ans = 0;
int N, K;

array<llt, 11> Fac {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};

public:
    long long countGoodIntegers(int n, int k) {
        if(1 == n){
            return 9 / k;
        }

        int m = (n + 1) / 2;
        int start = 1;
        llt ans = 0;
        for(int i=0;i<m;++i) start = start * 10;
        if(n & 1) m -= 1;
        
        set<llt> already;
        for(int v=start/10;v<start;++v){
            auto s = to_string(v);
            llt tmp = v;
            for(int i=m-1;i>=0;--i) tmp = tmp * 10 + (s[i] - '0');    
            if(tmp % k == 0){
                auto key = get(tmp);
                auto it = already.find(key);
                if(it != already.end()) continue;                
                already.insert(it, key);
                
                int cnt[10] = {0};
                for(int i=0;i<m;++i) cnt[s[i] - '0'] += 2;
                if(n & 1) cnt[s.back() - '0'] += 1;

                llt tmp = Fac[n];
                for(int i=0;i<10;++i) tmp /= Fac[cnt[i]];

                if(cnt[0]){
                    llt tt = Fac[n - 1];
                    tt /= Fac[cnt[0] - 1];
                    for(int i=1;i<10;++i) tt /= Fac[cnt[i]];
                    tmp -= tt;
                } 

                ans += tmp;                
            }
        }

        return ans;
    }

    llt get(llt n){
        vi vec;
        while(n){
            vec.emplace_back(n % 10);
            n /= 10;
        }
        sort(vec.begin(), vec.end());
        llt ans = 0;
        for(auto i : vec) ans = ans * 10 + i;
        return ans;
    }
};
